import java.util.*;

class Person{
    public String id;

    public Person(String id){
        this.id = id;
    }

    //如果要用类到集合里进行比较，则需要重写equals hashcode
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class Test {

    //前K个高频单词
    //https://leetcode.cn/problems/top-k-frequent-words/description/
    //给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
    //返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
    //示例 1：
    //输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
    //输出: ["i", "love"]
    //解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    //    注意，按字母顺序 "i" 在 "love" 之前。
    //示例 2：
    //
    //输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
    //输出: ["the", "is", "sunny", "day"]
    //解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    //    出现次数依次为 4, 3, 2 和 1 次。
    //注意：
    //
    //1 <= words.length <= 500
    //1 <= words[i] <= 10
    //words[i] 由小写英文字母组成。
    //k 的取值范围是 [1, 不同 words[i] 的数量]
    //进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
    public List<String> topKFrequent(String[] words,int k){
        HashMap<String,Integer> map = new HashMap<>();
        for (String word: words) {
            if (map.get(word) == null){
                map.put(word,1);
            }else{
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //遍历map
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if(top.getValue().compareTo(entry.getValue()) == 0) {
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> list = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }
        //e-2 f-3 a-5
        Collections.reverse(list);
        return list;
    }





    //坏键盘打字
    //https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    //链接：https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    //来源：牛客网
    //旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。
    // 现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
    //肯定坏掉的那些键。
    //输入描述:
    //输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，
    // 由字母A-Z（包括大、小写）、数字0-9、
    //以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
    //输出描述:
    //按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。
    // 题目保证至少有1个坏键。
    //示例1
    //输入
    //7_This_is_a_test<br/>_hs_s_a_es
    //输出
    //7TI
    public static  void func(String str1,String str2){
        str1 = str1.toUpperCase();//转大写
        str2 = str2.toUpperCase();

        HashSet<Character> setAct = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char ch = str2.charAt(i);
            setAct.add(ch);
        }

        HashSet<Character> setBroken = new HashSet<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if (!setAct.contains(ch) && !setBroken.contains(ch)){
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }

    public static void main4(String[] args) {
        func("7_This_is_a_test","_hs_s_a_es");
    }


    //宝石与石头
    //https://leetcode.cn/problems/jewels-and-stones/description/
    // 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
    // stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    //字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
    //示例 1：
    //输入：jewels = "aA", stones = "aAAbbbb"
    //输出：3
    //示例 2：
    //输入：jewels = "z", stones = "ZZ"
    //输出：0
    public int numJewelsInStones(String jewels,String stones){
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            set.add(ch);
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            if (set.contains(ch)){
                count++;
            }
        }
        return count;

    }


    //复制带随机指针的链表
    //https://leetcode.cn/problems/copy-list-with-random-pointer/description/
    class Node {
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head){
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;

        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;

        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);

    }




    //只出现一次的数字
    //https://leetcode.cn/problems/single-number/description/
    //给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，
    // 其余每个元素均出现两次。找出那个只出现了一次的元素。
    //你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
    //示例 1 ：
    //输入：nums = [2,2,1]
    //输出：1
    //示例 2 ：
    //输入：nums = [4,1,2,1,2]
    //输出：4
    //示例 3 ：
    //输入：nums = [1]
    //输出：1
    public int singleNumber(int[] nums){
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }



    //统计每个单词出现的个数
    public static Map<String,Integer> countWord(String[] words){
        Map<String,Integer> map = new HashMap<>();
        for (String s:words) {
            if (map.get(s) == null){
                map.put(s,1);
            }else{
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        return map;
    }
    public static void main3(String[] args) {
        String[] words = {"hello","abc","hello","def","this","this","this"};
        Map<String ,Integer> map = countWord(words);
        Set<Map.Entry<String,Integer>> entryset = map.entrySet();
        for (Map.Entry<String,Integer> entry: entryset) {
            System.out.println("key: "+entry.getKey() +" val: "+entry.getValue());
        }
    }



    public static void main2(String[] args) {
        Person person1 = new Person("1234");
        Person person2 = new Person("1234");

        /*System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());

        System.out.println(person1.equals(person2));*/
        HashBuck2<Person,String> hashBuck2 = new HashBuck2<>();
        hashBuck2.push(person1,"xiaoming");

        System.out.println(hashBuck2.getVal(person2));

    }
    public static void main1(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.push(1,111);
        hashBuck.push(11,111111);
        hashBuck.push(14,141414);
        hashBuck.push(4,444);
        hashBuck.push(2,222);
        hashBuck.push(15,151515);
        hashBuck.push(6,666);
        hashBuck.push(5,555);

        System.out.println(hashBuck.getVal(15));

    }
}
